class Solution {
public:
    string longestPalindrome(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function

		int n = s.length();
		int ans_l = -1;
		int ans_r = -1;
		for (int i = 0; i < n; ++i) {
			int l = i;
			int r = i;
			while (l >= 0 && r < n && s[l] == s[r]) {
				--l;
				++r;
			}
			++l;
			--r;
			if (ans_l < 0 || r - l + 1 > ans_r - ans_l + 1) {
				ans_r = r;
				ans_l = l;
			}

			if (i - 1 < 0 || s[i - 1] != s[i]) {
				continue;
			}
			l = i - 1;
			r = i;
			while (l >= 0 && r < n && s[l] == s[r]) {
				--l;
				++r;
			}
			++l;
			--r;
			if (ans_l < 0 || r - l + 1 > ans_r - ans_l + 1) {
				ans_r = r;
				ans_l = l;
			}
		}
		return s.substr(ans_l, ans_r - ans_l + 1);
    }
};